function getElement(targetArray, operatedStruct) {
  // 递归把operatedStruct中的数据（可以包含可迭代项）插入到targetArray中
  Array.from(operatedStruct).forEach(item => {
    if (item instanceof Array) return getElement(targetArray, item)
    targetArray[targetArray.length] = item
  })
}

function ArrayList() {
  this.array = []

  ArrayList.prototype.insert = function() {
    getElement(this.array, arguments)
    return this
  }

  ArrayList.prototype.toString = function(punctuation) {
    return this.array.join(punctuation)
  }

  // 实现排序算法
  // 1.冒泡排序
  ArrayList.prototype.bubbleSort = function() {
    for (let i = 0; i < this.array.length; i++) {
      for (let j = i + 1; j < this.array.length; j++) {
        if (this.array[j] < this.array[i]) this.swap(i, j)
      }
    }
    return this.array
  }

  // 2.选择排序
  ArrayList.prototype.selectionSort = function() {
    let index = 0
    while (index < this.array.length - 1) {
      let minIndex = index // 记录每次要替换的元素的索引
      for (let i = minIndex + 1; i < this.array.length; i++) {
        if (this.array[i] < this.array[minIndex]) minIndex = i
      }
      this.swap(minIndex, index++)
    }
    return this.array
  }

  // 3.插入排序
  ArrayList.prototype.insertionSort = function() {
    for (let i = 1; i < this.array.length; i++) {
      let flag = true // 记录是否找到了比temp小的值
      let temp = this.array[i]
      for (let j = i - 1; j >= 0; j--) {
        if (this.array[j] >= temp) {
          this.array[j + 1] = this.array[j]
        } else {
          // 找到了比temp小的值
          flag = false
          this.array[j + 1] = temp
          break
        }
      }
      // 遍历完有序部分仍未发现比temp小的值
      if (flag) this.array[0] = temp
    }
    return this.array
  }

  // 4.希尔排序
  ArrayList.prototype.shellSort = function() {
    // 初始化增量
    let gap = Math.floor(this.array.length / 2)
    while (gap >= 1) {
      for (let i = gap; i < this.array.length; i++) {
        let temp = this.array[i]
        let flag = true // 记录是否找到了比temp更小的值
        for (var j = i - gap; j >= 0; j -= gap) {
          if (this.array[j] >= temp) {
            this.array[j + gap] = this.array[j]
          } else {
            flag = false
            this.array[j + gap] = temp
            break
          }
        }
        if (flag) this.array[j + gap] = temp
      }
      gap = Math.floor(gap / 2)
    }
    return this.array
  }

  // 5.快速排序
  ArrayList.prototype.quickSort = function() {
    this.quick(0, this.array.length - 1)
    return this.array
  }

  ArrayList.prototype.quick = function(left, right) {
    // 1.结束条件
    if (left >= right) return
    let pivot = this.medium(left, right) // 取出枢纽并把枢纽排在了right的前一位
    let pointerLeft = left
    let pointerRight = right - 1
    while (true) {
      while (this.array[++pointerLeft] < pivot) {}
      while (this.array[--pointerRight > pivot]) {}
      if (pointerLeft < pointerRight) {
        this.swap(pointerLeft, pointerRight)
      } else {
        break
      }
    }
    this.swap(pointerLeft, right - 1)
    this.quick(left, pointerLeft - 1)
    this.quick(pointerLeft + 1, right)
  }

  // 选择排序选择枢纽
  ArrayList.prototype.medium = function(left, right) {
    let center = Math.floor((left + right) / 2)

    // 取得三个数对应数组得中位数(顺带排序)
    if (this.array[left] > this.array[center]) this.swap(left, center)
    if (this.array[center] > this.array[right]) this.swap(center, right)
    if (this.array[left] > this.array[center]) this.swap(left, center)
    this.swap(center, right - 1)
    return this.array[right - 1]
  }

  ArrayList.prototype.swap = function(a, b) {
    let temp = this.array[a]
    this.array[a] = this.array[b]
    this.array[b] = temp
  }
}

let a = new ArrayList()

a.insert(6, 5, 2, 26, 13, 9 - 12, 55) // 有重复的怎么办?
console.log(a.toString());
// console.log(a.medium(0, 2));

// console.log(a.bubbleSort());
// console.log(a.selectionSort());
// console.log(a.insertionSort());
// console.log(a.shellSort());
console.log(a.quickSort());

// 简单排序
// 冒泡排序比较的次数 ----> (n-1)*n/2 ---> O(n²)
// 交换的次数 ----> (n-1)*n/4 ----> O(n²)

// 选择排序比较的次数 ----> (n-1)*n/2 ---> O(n²)
// 交换的次数 ----> n ---> O(n)

// 插入排序比较的次数 ----> ((n-1)*n/2 + 0) / 2 = (n-1)*n / 4 ---> O(n²)
// 复制的次数 ----> ((n-1)*n/2 + 0) / 2 = (n-1)*n / 4 ---> O(n²)

// 插入排序效率最高（复制消耗的性能少于交换），对于数据有序的情况，性能高出很多

// 希尔排序最坏情况下是O(n²),高于简单排序